home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 2282 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.7 KB
  1. Path: keats.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Algorithm - intersection of lines!
  5. Date: 19 Jan 1996 15:23:03 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4dp94nINN822@keats.ugrad.cs.ubc.ca>
  8. References: <4bebi9$eik@news.infi.net> <e3f_9601030228@tor250.org> <4crl7v$bju@news.microsoft.com>
  9. NNTP-Posting-Host: keats.ugrad.cs.ubc.ca
  10.  
  11. In article <4crl7v$bju@news.microsoft.com>,
  12. Dann Corbit <a-cnadc@microsoft.com> wrote:
  13. >In article <e3f_9601030228@tor250.org>, Philip.Davis@fknights.gryn.org says...
  14. >>
  15. >> nn> Finding the intersection of lines is not trivial.
  16. >>
  17. >>But if you have the equations of the lines, can't you simply set the 
  18. >>equations equal, and solve for x and y (which gives the point of 
  19. >>intersection...)  just some grade 11 math which occurred to me.
  20. >
  21. >Parralel?  Infinite or zero slope?  Not in the same plane?  
  22.  
  23. If they are not in the same plane, you are dealing with 3-D intersections, for
  24. which you can use a different approach. I don't have access to the original
  25. post, so I don't know which was being called for.
  26.  
  27. If you define a (2D) line as an implicit equation in the form Ax + By + D = 0,
  28. you never run into problem stemming from zero or infinite slope. One would
  29. have to be quite naive to try to represent the line as y = mx + b!
  30.  
  31. A line with an infinite slope just has a left or right pointing normal
  32. vector; that is, <A, B> = <N, 0>, where N is some non-zero number.
  33. The equation looks like Ax + 0y + D = 0, and its treatment presents no special
  34. problem. A line with zero slope is just of the form 0x + By + D = 0.
  35.  
  36. >Numerically parallel? Coincident?
  37.  
  38. This can be checked by looking at the normal vectors, <A1, B1> and <A2, B2>.
  39. If these are parallel, the lines are parallel. You simply check whether
  40. the dot product of <A1, B1> and <-B2, A2> is zero. No need to worry about
  41. infinite or zero slopes.  No division required.
  42.  
  43. To check if the lines are coincident, first check whether they are parallel. If
  44. so, check if the both share a point. Substitute a point that you know is on
  45. either line into the implicit equation of the other, and check that it it is
  46. within some tolerance of zero.  For this, it may be useful to have an arbitrary
  47. point on the line as part of your data structure.
  48.  
  49. >Not trivial.  An intersection routine can be fairly compact, but
  50. >a good one will definitely require some careful thinking.
  51.  
  52. True, but it is a fairly easy problem to solve. You don't need any heavy
  53. numerical analysis, just bit of linear algebra and common sense.
  54.  
  55. To do the 3D version of the problem, it's probably best to think of one of
  56. the lines as a parametrized ray, and the other as a cylinder of some finite
  57. thickness.
  58. -- 
  59.  
  60.